package com.sicheng.algorithm.recursive.dfs;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/1/28 12:17
 */
public class 子集 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 3};
        List<List<Integer>> lists = solution.subsets(nums);
        System.out.println(lists);
    }

    static class Solution {
        List<List<Integer>> res = new ArrayList<>();
        ArrayDeque<Integer> path = new ArrayDeque<>();

        public List<List<Integer>> subsets(int[] nums) {
            Arrays.sort(nums);
            dfs(nums, 0);
            return res;
        }

        public void dfs(int[] nums, int start) {
            res.add(new ArrayList<>(path));
            if (start == nums.length)
                return;
            for (int i = start; i < nums.length; i++) {
                if (!path.contains(nums[i]) && maxInPath(nums[i])) {
                    path.addLast(nums[i]);
                    dfs(nums, start + 1);
                    path.removeLast();
                }

            }
        }

        private boolean maxInPath(int num) {
            for (Integer integer : path) {
                if (num <= integer) {
                    return false;
                }
            }
            return true;
        }
    }

}
